import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/8/6
 * Time: 20:15
 */
public class Solution {
    /*public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][2];
        //按照子数组的左端点的大小进行排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        //创建顺序表来存放子数组
        List<int[]> ret = new ArrayList<>();
        //遍历二维数组
        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            //当ret为空或者ret中最后一个元素的 右端点 小于 当前left时,向ret添加元素
            if (ret.isEmpty() || ret.get(ret.size() - 1)[1] < left) {
                ret.add(new int[]{left, right});
            } else {
                //将ret中最后一个元素的右端点和right比较,取较大值代替ret中最后一个元素的右端点
                ret.get((ret.size() - 1))[1] = Math.max(ret.get(ret.size() - 1)[1], right);
            }
        }
        //将顺序表转换为二维数组
        return ret.toArray(new int[ret.size()][]);
    }*/

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (v1,v2) -> Integer.compare(v1[0], v2[0]));
        int left = intervals[0][0], right = intervals[0][1];
        List<int[]> result = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int curLeft = intervals[i][0], curRight = intervals[i][1];
            if (curLeft <= right){
                right = Math.max(right, curRight);
            }else {
                result.add(new int[]{left, right});
                left = curLeft;
                right = curRight;
            }
        }
        result.add(new int[]{left, right});
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] merge = solution.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        System.out.println(Arrays.deepToString(merge));
    }
}
